package test;

//爱吃香蕉的珂珂：https://leetcode.cn/problems/koko-eating-bananas/

//时间复杂度： O(n*log(max)),空间复杂度：O(1)
public class MinEatingSpeed {
	//给定速度speed，返回吃完所有香蕉的时间
	public long f(int[] piles,int speed){
        long tmp=0;
        for(int i=0;i<piles.length;i++){
            tmp+=(piles[i]+speed-1)/speed; //向上取整
        }
        return tmp;
    }
    public int minEatingSpeed(int[] piles, int h) {
    	//答案区间[l,r]=[1,max(piles[i])]
        int l=1,r=0;
        int ret=Integer.MAX_VALUE;
        for(int x:piles){
            r=Math.max(x,r);
        }
        //二分答案
        while(l<=r){
            int mid=l+(r-l)/2;
            if(f(piles,mid)<=h){
                ret=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return ret;
    }
}
